package com.qq.BFMRSE.entity;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

import com.sun.rmi.rmid.ExecOptionPermission;
public class indexTree implements Serializable {
	private static final long serialVersionUID = 3L;
	private indexTreeNode root;
	public indexTree(){}
	public indexTree(indexTreeNode root)
	{
		this.root=root;
	} 
	public indexTreeNode getRoot()
	{
		return root;
	}
	public void setIndexNode(indexTreeNode root)
	{
		this.root=root;
	}
	/**
	 * 返回节点的高度
	 * @param node
	 * @return
	 */
	public int getTreeDepth(indexTreeNode node)
	{
		int leftDepth=0;
		int rightDepth=0;
		if(node==null)
		{
			return 0;
		}
		else {
			leftDepth=getTreeDepth(node.getLeft())+1;
			rightDepth=getTreeDepth(node.getRight())+1;
			return leftDepth>rightDepth?leftDepth:rightDepth;
		}
	}
	/**
	 * 返回节点的高度
	 * @param node
	 * @return
	 */
	public int getNodeHeight(indexTreeNode node)
	{
		int height=0;
		indexTreeNode currNode=node;
		while(currNode!=null)
		{
			if(currNode==root)
			{
				height++;
				break;
			}
			currNode=currNode.getParent();
			height++;
			
		}
		return height;
		
	}
	/**
	 * 构建平衡二叉树
	 * @param queue
	 */
	public void buildBalanceBinTree(Queue<indexTreeNode> queue)
	{
		Queue<indexTreeNode> currNodeSet=queue;
		Queue<indexTreeNode> tempNodeSet=new LinkedBlockingQueue<indexTreeNode>();
		indexTreeNode tempNode1=new indexTreeNode();
		indexTreeNode tempNode2=new indexTreeNode();
		indexTreeNode newNode=new indexTreeNode();
		while(currNodeSet.size()>1)
		{
			if(currNodeSet.size()%2==0)
			{
				while(!currNodeSet.isEmpty())
				{
					tempNode1=currNodeSet.poll();
					tempNode2=currNodeSet.poll();
					newNode=getNewNode(tempNode1, tempNode2);
					tempNode1.setParent(newNode);
					tempNode2.setParent(newNode);
					tempNodeSet.add(newNode);
				}
			}
			else {
				while(currNodeSet.size()>3)
				{
					tempNode1=currNodeSet.poll();
					tempNode2=currNodeSet.poll();
				    newNode=getNewNode(tempNode1, tempNode2);
					tempNode1.setParent(newNode);
					tempNode2.setParent(newNode);
					tempNodeSet.add(newNode);
				}
				tempNode1=currNodeSet.poll();
				tempNode2=currNodeSet.poll();
				newNode=getNewNode(tempNode1, tempNode2);
				tempNode1.setParent(newNode);
				tempNode2.setParent(newNode);
				tempNode1=newNode;
				tempNode2=currNodeSet.poll();
				newNode=getNewNode(tempNode1, tempNode2);
				tempNode1.setParent(newNode);
				tempNode2.setParent(newNode);
				tempNodeSet.add(newNode);
			}
			int count=tempNodeSet.size();
			for(int i=0;i<count;i++)
			{
				currNodeSet.add(tempNodeSet.poll());
			}
			tempNodeSet.clear();
		}
		root=currNodeSet.poll();
	}
	/**
	 *根据node1和node2生成新的节点
	 * @param node1
	 * @param node2
	 * @return
	 */
	public  indexTreeNode getNewNode(indexTreeNode node1,indexTreeNode node2)
	{
		indexTreeNode newNode=new indexTreeNode();
		newNode.setLeft(node1);
		newNode.setRight(node2);
		BloomFilter tempbf=new BloomFilter();
		BitSet tempBloomFilter=new BitSet();
		int length=node1.getBf().BitsLength();
		for(int i=0;i<length;i++)
		{
			if(node1.getBf().getBits().get(i)==true||node2.getBf().getBits().get(i)==true)
			{
				tempBloomFilter.set(i, true);
			}
			else {
				tempBloomFilter.set(i, false);
			}
		}
		tempbf.setBits(tempBloomFilter);
		newNode.setBf(tempbf);
		return newNode;
	}
	public List<String> searchOverTree(indexTreeNode node,BloomFilter searchBF)
	{
		List<String> fileList=new ArrayList<String>();
		Queue<indexTreeNode>queue=new LinkedBlockingQueue<indexTreeNode>();
		indexTreeNode currNode=node;
		if(currNode!=null)
		{
			queue.add(currNode);
		}
		while(!queue.isEmpty())
		{
			currNode=queue.poll();
			if(isContinueSearch(searchBF, currNode.getBf()))
			{
				if(isLeaf(currNode))
				{
					fileList.add(currNode.getFID());
				}
				else {
					if(currNode.getLeft()!=null)
					{
						indexTreeNode templeft=currNode.getLeft();
						queue.add(templeft);
					}
					if(currNode.getRight()!=null)
					{
						indexTreeNode tempRight=currNode.getRight();
						queue.add(tempRight);
					}
				}
			}
			
		}
		return fileList;
	}
	public boolean isContinueSearch(BloomFilter searchBF,BloomFilter nodebf)
	{
		boolean isContinue=false;
		int length=searchBF.getBits().length();
		int hashCount=searchBF.hashCount();
		int flag=0;
		for(int i=0;i<length;)
		{
			int j=searchBF.getBits().nextSetBit(i);
			if(nodebf.getBits().get(j))
			{
				flag++;
				if(flag==hashCount)
				{
					isContinue=true;
					break;
				}
			}
			i=j+1;
		}
		return isContinue;
	}
	public void levelOrder(indexTreeNode node)
	{
		Queue<indexTreeNode> queue=new LinkedBlockingQueue<indexTreeNode>();
		indexTreeNode currNode=node;
		if(currNode!=null)
		{
			queue.add(currNode);
		}
		while(!queue.isEmpty())
		{
			currNode=queue.poll();
			visit(currNode);
			if(currNode.getLeft()!=null)
			{
				queue.add(currNode.getLeft());
			}
			if(currNode.getRight()!=null)
			{
				queue.add(currNode.getRight());
			}
		}
		
	}
	public void postOrderNoTraverse(indexTreeNode node)
	{
		Stack< indexTreeNode>stack=new Stack<indexTreeNode>();
		indexTreeNode currNode=node;
		indexTreeNode preNode=null;
		while(!stack.isEmpty()||currNode!=null)
		{
			while(currNode!=null)
			{
				stack.push(currNode);
				currNode=currNode.getLeft();
			}
			currNode=stack.peek();
			if(currNode.getRight()==null||currNode.getRight()==preNode)
			{
				//currNode=stack.pop();
				visit(currNode);
				preNode=currNode;
				stack.pop();
				currNode=null;
			}
			else {
				currNode=currNode.getRight();
			}
			
		}
	}
	public void visit(indexTreeNode node)
	{
		if(node.getFID()!=null)
		{
			System.out.println(node.getFID());
		}
		else {
			System.out.println("");
		}
	}
	public int getNodeCount()
	{
		int count=0;
		indexTreeNode currNode=root;
		Queue<indexTreeNode>queue=new LinkedBlockingQueue<indexTreeNode>();
		if(currNode!=null)
		{
			queue.add(currNode);
		}
		while(!queue.isEmpty())
		{
			currNode=queue.poll();
			count++;
			if(currNode.getLeft()!=null)
			{
				queue.add(currNode.getLeft());
			}
			if(currNode.getRight()!=null)
			{
				queue.add(currNode.getRight());
			}
		}
		return count;
	}
	public boolean isLeaf(indexTreeNode node)
	{
		if(node.getLeft()==null&&node.getRight()==null)
		{
			return true;
		}
		else {
			return false;
		}
	}
	public indexTreeNode getChangedNode(indexTreeNode node)
	{
		indexTreeNode resultNode=null;
		int deepth=getTreeDepth(node);
		Queue<indexTreeNode>queue=new LinkedBlockingQueue<indexTreeNode>();
		indexTreeNode currNode=node;
		if(currNode!=null)
		{
			queue.add(currNode);
		}
		while(!queue.isEmpty())
		{
			currNode=queue.poll();
			if(getNodeHeight(currNode)<deepth)
			{
				if(currNode.getLeft()==null&&currNode.getRight()==null)
				{
					resultNode=currNode;
					break;
				}
				else {
					if(currNode.getLeft()!=null)
					{
						queue.add(currNode.getLeft());
					}
					if(currNode.getRight()!=null)
					{
						queue.add(currNode.getRight());
					}
				}
			}
		}
		if(resultNode==null)
		{
			resultNode=getALeafNode(node);
		}
		return resultNode;
	}
	public indexTreeNode getALeafNode(indexTreeNode node)
	{
		indexTreeNode resultNode=new indexTreeNode();
		indexTreeNode currNode=node;
		while(currNode!=null)
		{
			if(currNode.getRight()== null&&currNode.getRight()==null)
			{
				resultNode=currNode;
			}
			currNode=currNode.getLeft();
		}
		return resultNode;
		
	}
	public  void setAllNodeParent(indexTreeNode root)
	{
		indexTreeNode currNode=root;
		Queue<indexTreeNode>queue=new LinkedBlockingQueue<indexTreeNode>();
		if(currNode!=null)
		{
			queue.add(currNode);
		}
		while(!queue.isEmpty())
		{
			currNode=queue.poll();
			if(currNode.getLeft()!=null)
			{
				currNode.getLeft().setParent(currNode);
				queue.add(currNode.getLeft());
			}
			if(currNode.getRight()!=null)
			{
				currNode.getRight().setParent(currNode);
				queue.add(currNode);
			}
		}
	}
	public  Stack<Integer> getPathToChangedNode(indexTreeNode root,indexTreeNode node)
	{	
		System.out.println("test:getPathToChangedNode exec");
		Stack<Integer> resultStack=new Stack<Integer>();
		indexTreeNode currNode=node;
		while(currNode!=root)
		{
			if(currNode.getParent().getLeft()==currNode)
			{
				resultStack.push(0);
			}
			else {
				resultStack.push(1);
			}
			currNode=currNode.getParent();
		}	
		return resultStack;
	}
	public indexTreeNode getLeafNodeByFileName(indexTreeNode root,String fileName)
	{
		indexTreeNode leafNode=new indexTreeNode();
		indexTreeNode currNode=root;
		Queue<indexTreeNode>queue=new LinkedList<indexTreeNode>();
		if(currNode!=null)
		{
			queue.add(currNode);
		}
		while(!queue.isEmpty())
		{
			currNode=queue.poll();
			if(currNode.getLeft()==null&&currNode.getRight()==null)
			{
				if(currNode.getFID().equals(fileName))
				{
					leafNode=currNode;
					return leafNode;
				}
			}
			if(currNode.getLeft()!=null)
			{
				queue.add(currNode.getLeft());
			}
			if(currNode.getRight()!=null)
			{
				queue.add(currNode.getRight());
			}
		}
		return leafNode;
	}
	
}
